package com.leetcode.problems022;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public static final char LEFT = '(';

    public static final char RIGHT = ')';


    private List<String> resList = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if(n <= 0){
            return new ArrayList<>();
        }
        if(n == 1){
            return Arrays.asList("()");
        }
        generateParenthesis(n,n,new StringBuilder());
        return resList;
    }

    void generateParenthesis(int l,int r,StringBuilder res){
        if(l == 0 && r == 0){
            resList.add(res.toString());
            return ;
        }
       if(l > 0){
           res.append(LEFT);
           generateParenthesis(l - 1,r,res);
           res.deleteCharAt(res.length() - 1);
       }
       if(r > 0 && r > l){
            res.append(RIGHT);
            generateParenthesis(l,r - 1,res);
            res.deleteCharAt(res.length() - 1);
       }
    }
    public static void main(String[] args) {
        System.out.println(new Solution().generateParenthesis(2));
    }
}
